package leetcode_day._2021._202106._2130;

import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/6/25 21:50
 * 打开转盘锁
 * 算法：BFS
 * 跟 127 不同的是，本题中不能经过给定数组的值
 * 所以数据量会比较大
 */
public class _25_752 {

    public int openLock(String[] deadends, String target) {
        HashSet<String> wordSet = new LinkedHashSet<>(deadends.length);
        for (String s : deadends) {
            if ("0000".equals(s)) return -1;
            wordSet.add(s);
        }
        if ("0000".equals(target)) return 0;
        HashSet<String> visited = new LinkedHashSet<>();
        visited.add("0000");
        Queue<String> queue = new LinkedList<>();
        queue.offer("0000");
        int step = 0;
        while (!queue.isEmpty()) {
            int curSize = queue.size();
            for (int i = 0; i < curSize; i++) {
                String curWord = queue.poll();
                if (bfs(curWord, target, wordSet, visited, queue)) return step + 1;
            }
            ++step;
        }
        return -1;
    }
    boolean bfs(String curWord, String target, HashSet<String> wordSet, HashSet<String> visited, Queue<String> queue) {
        char[] array = curWord.toCharArray();
        for (int i = 0; i < array.length; i++) {
            char originChar = array[i];
            char[] ab = new char[2];
            ab[0] = ((char) (originChar + 1)) > '9' ? '0' : ((char) (originChar + 1));
            ab[1] = ((char) (originChar - 1)) < '0' ? '9' : ((char) (originChar - 1));
            for (int j = 0; j < 2; j++) {
                array[i] = ab[j];
                String s = new String(array);
                if (!wordSet.contains(s)) {
                    if (target.equals(s)) return true;
                    if (!visited.contains(s)) {
                        queue.offer(s);
                        visited.add(s);
                    }
                }
            }
            array[i] = originChar;
        }
        return false;
    }

}
